﻿//-----------------------------------------------------------------------
// <copyright file="Articulation.cs" company="Luboš Bretschnieder">
// Copyright (c) 2008 Luboš Bretschnieder, Licensed under the Apache License, Version 2.0.
// </copyright>
//-----------------------------------------------------------------------
namespace Graphs.Algorithms
{
    using System;
    using System.Collections.Generic;
    using UI;
    using UI.StatusBars;

    /// <summary>
    /// Graph articulations algorithm implementation
    /// </summary>
    public class Articulation : IAlgorithm
    {
        #region Private fileds

        /// <summary>List of articaluation.</summary>
        private List<Vertex> articulations;

        /// <summary>Listo of processed edges.</summary>
        private List<Edge> processedEdges;

        /// <summary>Stack of vertices.</summary>
        private Stack<Vertex> stack;

        /// <summary>List of steps.</summary>
        private List<AlgorithmStep> steps;

        /// <summary>Initial order of vertex.</summary>
        private int order;

        /// <summary>Initial vertex minimum.</summary>
        private int minimum;
        #endregion

        #region Public properties

        /// <summary>
        /// Gets or sets the graph.
        /// </summary>
        /// <value>The graph.</value>
        public Graph Graph
        { 
            private get; set;
        }

        /// <summary>
        /// Gets the steps.
        /// </summary>
        /// <value>The steps.</value>
        public List<AlgorithmStep> Steps
        {
            get { return this.steps; }
        }
        #endregion

        /// <summary>
        /// Finds all articulations.
        /// </summary>
        public void Execute()
        {
            this.Execute(this.Graph.SortedVertices.Keys[0]);
        }

        /// <summary>
        /// Finds all articulations starting in the specified vertex.
        /// </summary>
        /// <param name="startVertexName">The start vertex name.</param>
        public void Execute(string startVertexName)
        {
            this.Reset();
            Vertex startVertex = this.Graph.GetVertex(startVertexName) ?? this.Graph.SortedVertices.Values[0];

            startVertex.Order = this.order;
            startVertex.Minimum = this.minimum;
            startVertex.State = VertexState.Blue;

            this.stack.Push(startVertex);

            if (this.Graph.Vertices.Count > 2)
            {
                while (this.stack.Count > 0)
                {
                    this.MakeStep();
                }
            }
        }

        /// <summary>
        /// Resets the algorithm.
        /// </summary>
        public void Reset()
        {
            this.articulations = new List<Vertex>();
            this.processedEdges = new List<Edge>();
            this.stack = new Stack<Vertex>();
            this.steps = new List<AlgorithmStep>();
            this.order = 1;
            this.minimum = 1;
        }

        /// <summary>
        /// Makes the step.
        /// </summary>
        public void MakeStep()
        {
            List<IStatusBar> statusBars;

            if (this.steps.Count == 0)
            {
                statusBars = this.GetStatusBars();
                this.steps.Add(new AlgorithmStep(this.Graph.Clone(), statusBars));
            }

            Vertex lastVertex = this.stack.Peek();
            List<Vertex> connectedVertices = this.Graph.FindConnectedVertices(lastVertex, this.processedEdges);

            if (connectedVertices.Count == 0 && this.stack.Count == 2)
            {
                Vertex removed = this.stack.Pop();
                if (!this.articulations.Contains(removed))
                {
                    removed.State = VertexState.Grey;
                }

                lastVertex = this.stack.Peek();
                connectedVertices = this.Graph.FindConnectedVertices(lastVertex, this.processedEdges);

                if (connectedVertices.Count > 0)
                {
                    this.articulations.Add(lastVertex);
                    lastVertex.State = VertexState.Red;
                }

                this.Graph.GetEdge(removed, lastVertex).State = EdgeState.Grey;
            }

            // nowhere to go - get back!
            if (connectedVertices.Count == 0)
            {
                // 1. delete vertex
                Vertex deletedVertex = this.stack.Pop();
                if (!this.articulations.Contains(deletedVertex))
                {
                    deletedVertex.State = VertexState.Grey;
                }

                if (this.stack.Count > 1)
                {
                    Vertex ancestor = this.stack.Peek();

                    // 2. update minimum
                    if (ancestor.Minimum > deletedVertex.Minimum)
                    {
                        ancestor.Minimum = deletedVertex.Minimum;
                    }

                    // 3. check for articulation
                    if (ancestor.Order <= deletedVertex.Minimum)
                    {
                        this.articulations.Add(ancestor);
                        ancestor.State = VertexState.Red;
                    }

                    this.Graph.GetEdge(deletedVertex, ancestor).State = EdgeState.Grey;
                }
            }
            else
            {
                // theres still possibility to go somewhere
                Edge currentEdge = this.Graph.GetEdge(connectedVertices[0], lastVertex);

                if (this.stack.Contains(connectedVertices[0]))
                {
                    if (lastVertex.Minimum > connectedVertices[0].Order)
                    {
                        lastVertex.Minimum = connectedVertices[0].Order;
                    }

                    currentEdge.State = EdgeState.Green;
                }
                else
                {
                    connectedVertices[0].Order = ++this.order;
                    connectedVertices[0].Minimum = ++this.minimum;
                    connectedVertices[0].State = VertexState.Blue;
                    this.stack.Push(connectedVertices[0]);

                    currentEdge.State = EdgeState.Blue;
                }

                this.processedEdges.Add(currentEdge);
            }

            statusBars = this.GetStatusBars();
            this.steps.Add(new AlgorithmStep(this.Graph.Clone(), statusBars));
        }

        /// <summary>
        /// Gets the status bars.
        /// </summary>
        /// <returns>List of status bars</returns>
        private List<IStatusBar> GetStatusBars()
        {
            List<IStatusBar> statusBars = new List<IStatusBar>();
                
            Vertex[] reversedStack = this.stack.ToArray();
            Array.Reverse(reversedStack);
                
            VerticesStatusBar verticesStatusBar = new VerticesStatusBar { Label = "LIFO", Vertices = reversedStack };
            VerticesStatusBar articulationsStatusBar = new VerticesStatusBar { Label = "Articulations", Vertices = this.articulations.ToArray() };

            statusBars.Add(verticesStatusBar);
            statusBars.Add(articulationsStatusBar);
            return statusBars;
        }
    }
}